package leetcode.D2000.T1541;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-19 18:52:42 星期六
 */

class Solution {
    // 一刷
    /*public int minInsertions(String s) {
        int left = 0, right = 0, already = 0;
        for(int i=0; i<s.length(); ++i) {
            if (s.charAt(i) == '(') {
                if (right % 2 == 1) {
                    already++;
                    right--;
                }
                right += 2;
            } else {
                right--;
                if (right == -1) {
                    right = 1;
                    left++;
                }
            }
        }
        return left + right + already;
    }*/

    // 二刷
    public int minInsertions(String s) {
        int ans = 0, needRight = 0;
        for (int i=0; i<s.length(); ++i) {
            if (s.charAt(i) == '(') {
                if (needRight % 2 == 0) {
                    needRight += 2;
                } else {
                    needRight++;
                    ans++;
                }
            } else {
                if (needRight > 0)
                    needRight--;
                else {
                    ans++;
                    needRight++;
                }
            }
        }
        return ans + needRight;
    }
}